home *** CD-ROM | disk | FTP | other *** search
/ Magnum One / Magnum One (Mid-American Digital) (Disc Manufacturing).iso / d12 / snip9_91.arc / LASORT.C < prev    next >
C/C++ Source or Header  |  1991-09-17  |  12KB  |  238 lines
  1. /*********************************************************************/
  2. /*                                                                   */
  3. /*  This Program Written by Paul Edwards.                            */
  4. /*                                                                   */
  5. /*********************************************************************/
  6. /*********************************************************************/
  7. /*                                                                   */
  8. /*  licorice all sort - an O(N) sort program.  Version 1.31          */
  9. /*                                                                   */
  10. /*  This program takes the following parameters:                     */
  11. /*  1) base - A pointer to the start of your data                    */
  12. /*  2) n - number of elements to be sorted                           */
  13. /*  3) size - size of elements being sorted                          */
  14. /*  4) offset - number of bytes into the record                      */
  15. /*                                                                   */
  16. /*  Designed to be much like C's builtin qsort, this program sorts   */
  17. /*  into ascending order an array base[0]...base[n-1] of objects     */
  18. /*  size size.  (not a typo).                                        */
  19. /*                                                                   */
  20. /*  After my last aborted attempt at creating an original sort       */
  21. /*  program, here is a new one.  It is called lasort, short for      */
  22. /*  licorice all sort.                                               */
  23. /*                                                                   */
  24. /*  To sort an array of character strings, you first start off       */
  25. /*  looking at the first byte.  You create a table of statistics     */
  26. /*  (UCHAR_MAX entries) so that you know how many A's ther are etc.  */
  27. /*                                                                   */
  28. /*  It then once again traverses the list, knowing where to put      */
  29. /*  each element that is out of order.                               */
  30. /*                                                                   */
  31. /*  This code is dedicated to the public domain.  Do with it what    */
  32. /*  you will, but seeing as I invented it, it shall be known         */
  33. /*  hereafter as licorice all sort, and not by any other name.       */
  34. /*  The unusual name was suggested by my father, who preferred it    */
  35. /*  to death sort.  Also, a catchy name helps to make a sort         */
  36. /*  popular (ala bubble sort).                                       */
  37. /*                                                                   */
  38. /*  If you would like to contact me about this program, I normally   */
  39. /*  hang out on a bulletin board called Paragon, in Sydney,          */
  40. /*  Australia.  Fidonet address: 3:712/502                           */
  41. /*                                                                   */
  42. /*  licorice - I don't like it either.                               */
  43. /*                                                                   */
  44. /*  Written on 03-Oct-1989.                                          */
  45. /*                                                                   */
  46. /*  Copyright 1989 Paul Edwards.                                     */
  47. /*                                                                   */
  48. /*  Dedicated to my American friend Dan Malcolm, convinced           */
  49. /*  that Australians never write public domain software <grin>.      */
  50. /*                                                                   */
  51. /*  Version 1.3 enhancement.  When you have less than or equal to    */
  52. /*  RETIME records to sort, use Radix Exchange Sort instead.         */
  53. /*  When you have less than or equal to INTIME records to sort, use  */
  54. /*  Insertion Sort instead.                                          */
  55. /*                                                                   */
  56. /*  Version 1.31 fixed up void *, char *, unsigned char *            */
  57. /*                                                                   */
  58. /*********************************************************************/
  59. /* RETIME, INTIME are machine dependant, find values that suit you   */
  60. /* best.  List of possible optimum times for different machines:     */
  61. /* IBM XT compatible: RETIME 46, INTIME 7                            */
  62. #define RETIME 46       /* when radix is better than licorice */
  63. #define INTIME 7        /* when insertion sort is better than resort */
  64. #define MAX 300         /* maximum length of strings to be sorted */
  65. static char temp[MAX];  /* temporary storage for swap */
  66. #include <string.h>
  67. #include <limits.h>
  68. #include <assert.h>
  69. #include <stdlib.h>
  70. /*********************************************************************/
  71. /*                                                                   */
  72. /*  insertion sort - start from the bottom element (which is a       */
  73. /*  sorted array of length 1), then every time you move up one       */
  74. /*  element, you move it down (swapping with all elements below it)  */
  75. /*  until it is in its sorted position.                              */
  76. /*                                                                   */
  77. /*********************************************************************/
  78. void insort(void *base, int n, int size, int offset)
  79. {
  80.   register int j,rc,i;
  81.   for (i=0;i<n;i++)   /* moving up one element */
  82.   {
  83.     for (j=i;j>0;j--)  /* move down until in sorted order */
  84.     {
  85.       rc = memcmp((unsigned char *)base+j*size+offset,
  86.           (unsigned char *)base+(j-1)*size+offset,size-offset);
  87.       if (rc < 0)
  88.       {
  89.         /* swapping elements along the way */
  90.         memcpy(temp,(unsigned char *)base+j*size,size);
  91.         memcpy((unsigned char *)base+j*size,
  92.             (unsigned char *)base+(j-1)*size,size);
  93.         memcpy((unsigned char *)base+(j-1)*size,temp,size);
  94.       }
  95.       else break;
  96.     }
  97.   }
  98.   return;
  99. }
  100. /*********************************************************************/
  101. /*                                                                   */
  102. /*  radix exchange sort.  view one bit at a time, getting all '1'    */
  103. /*  bits up the top, and all the '0' bits down the bottom.           */
  104. /*                                                                   */
  105. /*********************************************************************/
  106. void resort(void *base, int n, int size, int offset)
  107. {
  108.   int bytesin;    /* no of bytes into the string */
  109.   int bitsin;     /* no of bits into the byte */
  110.   int p;          /* bottom element number */
  111.   int q;          /* top element number */
  112.   register unsigned char mask = 0x80;  /* bit we are interested in */
  113.   if (n <= 1) return;  /* we have finished this sub-sort if we have
  114.                           one or less elements to sort */
  115.   bytesin = offset / CHAR_BIT;  /* work out how many bytes we are
  116.              into the element by dividing by the number of bits we are
  117.              into the element by the number of bits in a byte */
  118.   if (bytesin == size) return;  /* we have just passed the length of the
  119.                                    data */
  120.   bitsin = offset % CHAR_BIT;  /* no of bits into the byte */
  121.   mask = mask >> bitsin;  /* mask masks the bit we are interested in */
  122.   p = 0;        /* low element starts at 0 */
  123.   q = n-1;      /* high element starts at n-1 */
  124.   while (p <= q)    /* until all swaps have been done */
  125.   {
  126.     while (((*((unsigned char *)base+p*size+bytesin) & mask) == 0)
  127.         && (p < n)) p++;   /* p will move up until it finds a bit that
  128.                               is not 0 (or until it reaches the top) */
  129.     /* q moves down until if finds a bit that is 0
  130.        (or until it reaches the bottom) */
  131.     while ((q >= 0) &&
  132.         ((*((unsigned char *)base+q*size+bytesin) & mask) != 0)) q--;
  133.     if (p < q)     /* p has a 1 bit and q has a 0 bit, so swap */
  134.     {
  135.       memcpy(temp,(unsigned char *)base+p*size,size);
  136.       memcpy((unsigned char *)base+p*size,
  137.           (unsigned char *)base+q*size,size);
  138.       memcpy((unsigned char *)base+q*size,temp,size);
  139.       p++;  /* p now points to a 0 bit, so move up one more */
  140.       q--;  /* q now points to a 1 bit, so move down one more */
  141.     }
  142.   }
  143.   /* sort lower numbers */
  144.   if (p <= INTIME) insort(base,p,size,(offset+1)/CHAR_BIT);
  145.   else resort((unsigned char *)base,p,size,offset+1);
  146.   /* sort higher numbers */
  147.   if ((n-p) <= INTIME)
  148.       insort((unsigned char *)base+p*size,n-p,size,(offset+1)/CHAR_BIT);
  149.   else resort((unsigned char *)base+p*size,n-p,size,offset+1);
  150.   return;
  151. }
  152. void lasort(void *base, int n, int size, int offset)
  153. {
  154.   int *stats; /* ptr to table of statistics (how many A's etc) */
  155.   unsigned char **subp; /* table of pointers to top of characters */
  156.   unsigned char **orgp; /* table of original pointers */
  157.   register int i;   /* used for many things */
  158.   register unsigned char critic;  /* character to be sorted */
  159.   register unsigned char *wereat; /* pointer to element we're up to */
  160.   assert((stats = malloc((UCHAR_MAX+1)*sizeof(*stats))) != NULL);
  161.   assert((subp = malloc((UCHAR_MAX+1)*sizeof(*subp))) != NULL);
  162.   assert((orgp = malloc((UCHAR_MAX+1)*sizeof(*orgp))) != NULL);
  163.   for (i=0;i<(UCHAR_MAX+1);i++) stats[i] = 0;  /* reset statistics */
  164.   for (i=0;i<n;i++)      /* create stats */
  165.       stats[*((unsigned char *)base+i*size+offset)]++;
  166.   orgp[0] = subp[0] = base;
  167.   /* create table of original pointers, and subpointers */
  168.   for (i=0;i<UCHAR_MAX;i++)
  169.       orgp[i+1] = subp[i+1] = subp[i] + size * stats[i];
  170.   for (i=0;i<n;)
  171.   {
  172.     /* start at bottom of table */
  173.     wereat = (unsigned char *)base+i*size;
  174.     critic = *(wereat+offset);  /* byte to put in sorted order */
  175.     if (wereat >= orgp[critic]) i++; /* is it already sorted? */
  176.     else
  177.     {
  178.       memcpy(temp,wereat,size); /* copy the record into temp */
  179.       memcpy(wereat,subp[critic],size); /* get unsorted back here */
  180.       memcpy(subp[critic],temp,size); /* put temp into sorted order */
  181.       subp[critic]+=size; /* next pointer will be one record up */
  182.     }
  183.   }
  184.   free(subp); /* don't need table of subpointers any more */
  185.   if (++offset < size)   /* if there are still more bytes in record */
  186.   {
  187.     for (i=0;i<(UCHAR_MAX+1);i++)
  188.     {
  189.       /* if there are sub-records of a character, sort them */
  190.       if (stats[i] > 1)
  191.       {
  192.         /* if there are less than INTIME records, use insort */
  193.         if (stats[i] <= INTIME) insort(orgp[i],stats[i],size,offset);
  194.         /* else if there are less than RETIME records, use resort */
  195.         else if (stats[i] <= RETIME)
  196.             resort(orgp[i],stats[i],size,offset*8);
  197.         else lasort(orgp[i],stats[i],size,offset);
  198.       }
  199.     }
  200.   }
  201.   free(stats); /* don't need table of statistics anymore */
  202.   free(orgp); /* don't need table of original pointers either */
  203.   return;
  204. }
  205. /* example of program that calls licorice all sort */
  206. #include <stdio.h>
  207. #include <stdlib.h>
  208. #include <assert.h>
  209. #include <time.h>
  210. main(int argc,char **argv)
  211. {
  212.   FILE *fp,*fq;
  213.   time_t t1,t2;
  214.   int numrec,lenrec;
  215.   char *myarr;
  216.   if (argc < 5)
  217.   {
  218.     printf("you must enter input file name, output file name\n");
  219.     printf("number of elements to read, length of elements\n");
  220.     printf("without making any mistakes\n");
  221.     return (1);
  222.   }
  223.   assert((fp = fopen(*(argv+1),"rb")) != NULL);
  224.   assert((fq = fopen(*(argv+2),"wb")) != NULL);
  225.   assert((numrec = atoi(*(argv+3))) != 0);
  226.   assert((lenrec = atoi(*(argv+4))) != 0);
  227.   assert((myarr = malloc(lenrec*numrec)) != NULL);
  228.   numrec = fread(myarr,lenrec,numrec,fp);
  229.   printf("%d records read in to licorice all sort\n",numrec);
  230.   time(&t1);
  231.   lasort((unsigned char *)myarr,numrec,lenrec,0);
  232.   time(&t2);
  233.   printf("licorice all sort took %d secs to process %d records\n",
  234.       (int)difftime(t2,t1),numrec);
  235.   fwrite(myarr,lenrec,numrec,fq);
  236.   return (0);
  237. }
  238.